// 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 动态规划，01背包,sum/2为背包容量，看物品能否把背包放满
// 看了题解

// 执行用时：
// 224 ms
// , 在所有 C++ 提交中击败了
// 46.62%
// 的用户
// 内存消耗：
// 9.7 MB
// , 在所有 C++ 提交中击败了
// 57.58%
// 的用户

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum =0;
        for(int i=0;i<nums.size();i++){
            sum = sum + nums[i];
        }
        int temp = sum%2;
        // 无法整除2直接false;
        if(temp==1){
            return false;
        }
        sum = sum/2;
        vector<int> dp(sum+1,0);
        // 一维01背包，物品在外，背包在内，且背包从大到小
        for(int i=0;i<nums.size();i++){
            // 背包容量大于等于物品才可以放
            for(int j=sum;j>=nums[i];j--){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return sum==dp[sum];
    }
};